<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40"><head>


<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="ProgId" content="Word.Document">
<meta name="Generator" content="Microsoft Word 9">
<meta name="Originator" content="Microsoft Word 9">
<link rel="File-List" href="http://uva.onlinejudge.org/external/106/d_files/filelist.xml">
<link rel="Edit-Time-Data" href="http://uva.onlinejudge.org/external/106/d_files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>Problem D: Prince and Princess</title>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>Shahriar Manzoor</o:Author>
  <o:LastAuthor>Shahriar Manzoor</o:LastAuthor>
  <o:Revision>12</o:Revision>
  <o:TotalTime>233</o:TotalTime>
  <o:LastPrinted>2002-10-30T23:30:00Z</o:LastPrinted>
  <o:Created>2004-03-02T07:28:00Z</o:Created>
  <o:LastSaved>2004-03-11T13:31:00Z</o:LastSaved>
  <o:Pages>2</o:Pages>
  <o:Words>338</o:Words>
  <o:Characters>1927</o:Characters>
  <o:Company>BUET</o:Company>
  <o:Lines>16</o:Lines>
  <o:Paragraphs>3</o:Paragraphs>
  <o:CharactersWithSpaces>2366</o:CharactersWithSpaces>
  <o:Version>9.2720</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:View>Print</w:View>
  <w:Zoom>BestFit</w:Zoom>
 </w:WordDocument>
</xml><![endif]-->
<style>
<!--
 /* Font Definitions */
@font-face
	{font-family:"MS Mincho";
	panose-1:2 2 6 9 4 2 5 8 3 4;
	mso-font-alt:"\FF2D\FF33 \660E\671D";
	mso-font-charset:128;
	mso-generic-font-family:modern;
	mso-font-pitch:fixed;
	mso-font-signature:647 134676480 16 0 131231 0;}
@font-face
	{font-family:"Beaconsfield Bold";
	panose-1:0 0 0 0 0 0 0 0 0 0;
	mso-font-charset:0;
	mso-generic-font-family:auto;
	mso-font-pitch:variable;
	mso-font-signature:7 0 0 0 19 0;}
@font-face
	{font-family:"\@MS Mincho";
	panose-1:0 0 0 0 0 0 0 0 0 0;
	mso-font-charset:128;
	mso-generic-font-family:roman;
	mso-font-format:other;
	mso-font-pitch:fixed;
	mso-font-signature:1 134676480 16 0 131072 0;}
 /* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
h1
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	text-align:center;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:1;
	font-size:100.0pt;
	mso-bidi-font-size:24.0pt;
	font-family:"Beaconsfield Bold";
	color:silver;
	mso-font-kerning:0pt;
	font-weight:bold;
	mso-bidi-font-weight:normal;}
h2
	{margin-right:0in;
	mso-margin-top-alt:auto;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	mso-outline-level:2;
	font-size:18.0pt;
	font-family:"Times New Roman";
	font-weight:bold;}
h3
	{margin-right:0in;
	mso-margin-top-alt:auto;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	mso-outline-level:3;
	font-size:13.5pt;
	font-family:"Times New Roman";
	font-weight:bold;}
h4
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:4;
	font-size:12.0pt;
	font-family:"Times New Roman";
	font-weight:normal;}
p.MsoBodyText, li.MsoBodyText, div.MsoBodyText
	{margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	mso-layout-grid-align:none;
	text-autospace:none;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.MsoBodyText2, li.MsoBodyText2, div.MsoBodyText2
	{margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	mso-layout-grid-align:none;
	text-autospace:none;
	font-size:12.0pt;
	mso-bidi-font-size:10.5pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	color:#333333;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";}
p
	{margin-right:0in;
	mso-margin-top-alt:auto;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
pre
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";}
tt
	{mso-ascii-font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";
	mso-hansi-font-family:"Courier New";
	mso-bidi-font-family:"Courier New";}
span.StyleArial16pt
	{mso-style-name:"Style Arial 16 pt";
	mso-ansi-font-size:16.0pt;
	mso-ascii-font-family:Arial;
	mso-hansi-font-family:Arial;
	mso-bidi-font-family:Arial;
	font-weight:bold;}
@page Section1
	{size:595.45pt 841.7pt;
	margin:.7in .8in .7in .8in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1038"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->
</head><body style="" lang="EN-US">

<div class="Section1">

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><span style="font-size: 28pt; font-family: Arial;">Problem D</span></b><span style="font-family: Arial;"><br>
</span><b style=""><span style="font-size: 20pt; font-family: Arial;">Prince and Princess</span></b><span style="font-family: Arial;"><br>
<b style="">Input: </b><span style="">Standard Input<o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><span style="font-family: Arial;">Output: </span></b><span style="font-family: Arial;">Standard Output<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><span style="font-family: Arial;">Time Limit: </span></b><span style="font-family: Arial;">3 Seconds<o:p></o:p></span></p>

<p class="MsoNormal" style=""><a name="SECTION0001001000000000000000"><span style="font-size: 10pt; font-family: &quot;Courier New&quot;;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></a></p>

<br style="" clear="ALL">

<p class="MsoBodyText"><span style="">In
an <b>n x n</b> chessboard, Prince and Princess plays a game. The squares in
the chessboard are numbered <b>1, 2, 3 ... n*n,</b> as shown below:</span></p>
<center><p>
<img src="acm-10635_files/p10635a.jpg" height="329" width="348">
</p></center>


<p class="MsoNormal" style="text-align: justify;"><span style=""><span style="">Prince stands in square <b>1</b>, make <b>p</b>
jumps and finally reach square <b>n*n</b>. He enters a square at most once. So
if we use <b>x</b></span></span><span style=""><b><sub><span style="font-size: 14pt;">p</span></sub></b></span><span style=""><span style=""> to
denote the <b>p</b>-th square he enters, then <b>x</b></span><b><sub>1</sub></b></span><span style=""><b><span style="">, x</span><sub>2</sub></b></span><span style=""><b><span style="">, ... x</span><sub>p+1</sub></b></span><span style=""><span style=""> are all different. Note that <b>x</b></span><b><sub>1</sub></b></span><span style=""><b><span style=""> = 1</span></b></span><span style=""><span style=""> and <b>x</b></span><b><sub>p+1</sub></b></span><span style=""><b><span style=""> = n*n</span></b></span><span style=""><span style="">. Princess does the similar thing - stands in
square <b>1</b>, make <b>q</b> jumps and finally reach square <b>n*n</b>. We
use <b>y</b></span><b><sub>1</sub></b></span><span style=""><b><span style="">, y</span><sub>2 </sub></b></span><span style=""><b><span style="">, ... y</span><sub>q+1</sub></b></span><span style=""><span style=""> to denote the sequence, and all <b>q+1</b>
numbers are different.<o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><span style=""><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><span style="">Figure <b>2</b> belows show a <b>3x3</b>
square, a possible route for Prince and a different route for Princess. <o:p></o:p></span></span></p>

<center>
<p><img src="acm-10635_files/p10635b.jpg" height="252" width="492"></p></center>
<p>
<span style="">The Prince moves along
the sequence: <b>1 --&gt; 7 --&gt; 5 --&gt; 4 --&gt; 8 --&gt; 3 --&gt; 9</b>
(Black arrows), while the Princess moves along this sequence: <b>1 --&gt; 4
--&gt; 3 --&gt; 5 --&gt; 6 --&gt; 2 --&gt; 8 --&gt; 9</b> (White arrow).</span></p>


<p class="MsoNormal" style="text-align: justify;"><span style="">The
King -- their father, has just come. "Why move separately? You are brother
and sister!" said the King, "Ignore some jumps and make sure that
you're always together."</span></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></p>

<p class="MsoBodyText"><span style=""><span style="">For example, if the Prince ignores his <b>2nd,
3rd, 6th</b> jump, he'll follow the route: <b>1 --&gt; 4 --&gt; 8 --&gt; 9</b>.
If the Princess ignores her <b>3rd, 4th, 5th, 6th</b> jump, she'll follow the
same route: <b>1 --&gt; 4 --&gt; 8 --&gt; 9</b>, (The common route is shown in
figure <b>3</b>) thus satisfies the King, shown above. The King wants to know
the longest route they can move together, could you tell him?<o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><span class="StyleArial16pt"><span style="font-size: 16pt; font-family: Arial;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><span class="StyleArial16pt"><span style="font-size: 16pt; font-family: Arial;">Input</span></span></span><span class="StyleArial16pt"><span style="font-size: 16pt; font-family: Arial;">&nbsp; </span></span><span class="StyleArial16pt"><span style="font-family: Arial;"><o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><a name="SECTION0001002000000000000000"><span style="">The first line of the input contains a single
integer <b>t(1 &lt;= t &lt;= 10)</b>, the number of test cases followed. For
each case, the first line contains three integers <b>n, p, q(2 &lt;= n &lt;=
250, 1 &lt;= p, q &lt; n*n)</b>. The second line contains <b>p+1</b> different
integers in the range <b>[1..n*n]</b>, the sequence of the Prince. The third
line contains <b>q+1</b> different integers in the range <b>[1..n*n]</b>, the
sequence of the Princess.<o:p></o:p></span></a></p>

<p class="MsoNormal" style="text-align: justify;"><span style=""><span style="">&nbsp;<o:p></o:p></span></span></p>

<h4><span style=""><span class="StyleArial16pt"><span style="font-size: 16pt; font-family: Arial;">Output</span></span></span><span class="StyleArial16pt"><span style="font-size: 16pt; font-family: Arial;">&nbsp;<o:p></o:p></span></span></h4>

<p class="MsoBodyText" style="">For
each test case, print the case number and the length of longest route. Look at
the output for sample input for details.</p>

<p class="MsoBodyText" style=""><b style=""><span style="font-size: 11pt; font-family: Arial;">&nbsp;<o:p></o:p></span></b></p>

<h1 style="text-align: left;" align="left"><span style="font-size: 16pt; font-family: Arial; color: black;">Sample Input<span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>Output for Sample
Input<o:p></o:p></span></h1>

<table style="border: medium none ; background: rgb(204, 204, 204) none repeat scroll 0% 0%; -moz-background-clip: border; -moz-background-origin: padding; -moz-background-inline-policy: continuous; border-collapse: collapse;" bgcolor="#cccccc" border="1" cellpadding="0" cellspacing="0">
 <tbody><tr>
  <td style="border: 0.5pt solid windowtext; padding: 0in 5.4pt; width: 221.4pt;" valign="top" width="295">
  <p class="MsoPlainText"><b><span style="font-size: 11pt;">1<o:p></o:p></span></b></p>
  <p class="MsoPlainText"><b><span style="font-size: 11pt;">3 6 7<o:p></o:p></span></b></p>
  <p class="MsoPlainText"><b><span style="font-size: 11pt;">1 7 5 4 8 3 9<o:p></o:p></span></b></p>
  <p class="MsoPlainText"><b><span style="font-size: 11pt;">1 4 3 5 6 2 8 9<o:p></o:p></span></b></p>
  <!--p class=MsoPlainText><b><span style='font-size:11.0pt;mso-bidi-font-size:
  10.0pt;mso-fareast-font-family:"MS Mincho"'>10 9 9<o:p></o:p></span></b></p>
  <p class=MsoPlainText><b><span style='font-size:11.0pt;mso-bidi-font-size:
  10.0pt;mso-fareast-font-family:"MS Mincho"'>1 2 3 4 5 6 7 8 9 10<o:p></o:p></span></b></p>
  <p class=MsoPlainText><b><span style='font-size:11.0pt;mso-bidi-font-size:
  10.0pt;mso-fareast-font-family:"MS Mincho"'>1 2 3 4 5 6 7 8 9 10<o:p></o:p></span></b></p>
  <p class=MsoPlainText><b><span style='font-size:11.0pt;mso-bidi-font-size:
  10.0pt;mso-fareast-font-family:"MS Mincho"'>4 2 2<o:p></o:p></span></b></p>
  <p class=MsoPlainText><b><span style='font-size:11.0pt;mso-bidi-font-size:
  10.0pt;mso-fareast-font-family:"MS Mincho"'>1 2 4<o:p></o:p></span></b></p>
  <pre><b><span style='font-size:11.0pt;mso-bidi-font-size:10.0pt;mso-fareast-font-family:
  "MS Mincho"'>1 3 4</span></b><b><span style='mso-bidi-font-size:12.0pt'><o:p></o:p></span></b></pre></td-->
  </td><td style="border-style: solid solid solid none; border-color: windowtext windowtext windowtext -moz-use-text-color; border-width: 0.5pt 0.5pt 0.5pt medium; padding: 0in 5.4pt; width: 240.85pt;" valign="top" width="321">
  <p class="MsoPlainText" style=""><b><span style="font-size: 11pt;">Case 1: 4<o:p></o:p></span></b></p>
  <!--p class=MsoPlainText style='tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><b><span
  style='font-size:11.0pt;mso-bidi-font-size:10.0pt;mso-fareast-font-family:
  "MS Mincho"'>Case 2: 10<o:p></o:p></span></b></p>
  <p style='margin:0in;margin-bottom:.0001pt;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><b><span
  style='font-size:11.0pt;mso-bidi-font-size:12.0pt;font-family:"Courier New";
  mso-fareast-font-family:"MS Mincho"'>Case 3: 2</span></b><b><span
  style='font-size:11.0pt;mso-bidi-font-size:10.0pt;font-family:"Courier New"'><o:p></o:p></span></b></p>
  <p class=MsoNormal style='tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><![if !supportEmptyParas]>&nbsp;<![endif]><b><span
  style='font-size:11.0pt;mso-bidi-font-size:12.0pt;font-family:"Courier New"'><o:p></o:p></span></b></p-->
  </td>
 </tr>
</tbody></table>


<div class="MsoNormal" style="text-align: center;" align="center"><span style="color: black;" lang="EN">

<hr size="2" width="100%" align="center">

</span></div>

<pre><b style=""><span style="font-size: 12pt; font-family: Arial;">Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel<o:p></o:p></span></b></pre><pre><span style="font-size: 12pt; font-family: Arial;">Pictures drawn by</span><b style=""><span style="font-size: 12pt; font-family: Arial;"> Shahriar Manzoor</span></b><span style="font-size: 12pt; font-family: Arial;">, Member of Elite Problemsetters' Panel</span><b style=""><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;;"><o:p></o:p></span></b></pre></div>
<br><br><center>
"What was lost was found; what was found was never lost."
</center>
</body></html>